package com.mdnote.structure.recuirsion;

import java.util.*;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/24
 * @description 迷宫问题哦 最短距离
 */
public class MazeQuestionMinDistance {

    private int[][] maze;

    public MazeQuestionMinDistance(int width, int height) {
        this.maze = new int[width][height];
    }

    /**
     * 设置障碍物
     * @param x 横坐标
     * @param y 纵坐标
     */
    public void setHinder(int x, int y) {
        this.maze[x][y] = 1;
    }

    public boolean go(int fromX, int fromY, int toX, int toY, Map.Entry<String, Integer> entry) {

        // TTerminate
        if (fromX == toX && fromY == toY) {
            return true;
        }

        // 1 墙壁  2 走过  3 死路
        // 没有做过
        if (this.maze[fromX][fromY] == 0) {
            // 假定走过了能走通
            if (this.maze[fromX][fromY] == 0) {
                // 假定走过了能走通
                this.maze[fromX][fromY] = 2;
                String strategy = entry.getKey();
                for (int i = 0; i < strategy.length(); i++) {
                    // 向下走
                    if (strategy.charAt(i) == '1' && go(fromX + 1, fromY, toX, toY, entry)) {
                        entry.setValue(entry.getValue() + 1);
                        return true;
                    }
                    // 向右走
                    if (strategy.charAt(i) == '2' && go(fromX, fromY + 1, toX, toY, entry)) {
                        entry.setValue(entry.getValue() + 1);
                        return true;
                    }
                    // 向上走
                    if (strategy.charAt(i) == '3' && go(fromX - 1, fromY, toX, toY, entry)) {
                        entry.setValue(entry.getValue() + 1);
                        return true;
                    }
                    // 向左走
                    if (strategy.charAt(i) == '4' && go(fromX, fromY - 1, toX, toY, entry)) {
                        entry.setValue(entry.getValue() + 1);
                        return true;
                    }
                }
            } else {
                // 做过了或者是死路
                this.maze[fromX][fromY] = 3;
            }
            return false;
        } else {
            // 做过了或者是死路
            this.maze[fromX][fromY] = 3;
        }
        return false;
    }

    /**
     * 展示迷宫
     */
    public void show() {
        for (int i = 0; i < this.maze.length; i++) {
            for (int j = 0; j < this.maze[0].length; j++) {
                System.out.print(this.maze[i][j] + " ");
            }
            System.out.println();
        }
    }

    
    public static void main(String[] args) {
        MazeQuestionMinDistance mazeQuestion = new MazeQuestionMinDistance(8, 8);
        reset(mazeQuestion);

        mazeQuestion.show();

        System.out.println("-------------------------");

        HashMap<String, Integer> combination = new HashMap<>();
        List<Integer> tempList = Arrays.asList(1, 2, 3, 4);
        // 生成随机数
        getCombination(new ArrayList<>(tempList), 0, 4, combination, "");
        for (Map.Entry<String, Integer> entry : combination.entrySet()) {
            // 将数字转换为具体的策略
            mazeQuestion.go(1, 1, 6, 5, entry);
            // 重置一下迷宫
            reset(mazeQuestion);
            // 将值写回Map
            System.out.println(entry.getKey() + "-->" + entry.getValue());
        }

    }

    /**
     * 重置迷宫
     * @param mazeQuestion 迷宫
     */
    private static void reset(MazeQuestionMinDistance mazeQuestion) {
        for (int i = 0; i < mazeQuestion.maze.length; i++) {
            for (int j = 0; j < mazeQuestion.maze[0].length; j++) {
                mazeQuestion.maze[i][j] = 0;
            }
        }

        // 设置墙壁
        for (int i = 0; i < 8; i++) {
            mazeQuestion.setHinder(i, 0);
            mazeQuestion.setHinder(i, 7);
        }
        for (int i = 0; i < 8; i++) {
            mazeQuestion.setHinder(0, i);
            mazeQuestion.setHinder(7, i);
        }
        mazeQuestion.setHinder(2, 1);
        mazeQuestion.setHinder(2, 2);
        mazeQuestion.setHinder(3, 3);
    }

    /**
     * 产生1 2 3 4的随机组合
     * @param data 数组
     * @param level 当前层数
     * @param maxLevel 最大层数
     * @param combination 值
     * @param
     */
    private static void getCombination(List<Integer> data, int level, int maxLevel, HashMap<String, Integer> combination, String res) {
        // Terminate
        if (level == maxLevel) {
            combination.put(res, 0);
        } else {
            // current logic
            // drill down
            for (int i = 0; i < data.size(); i++) {
                Integer temp = data.remove(i);
                getCombination(data, level + 1, maxLevel, combination, res + temp);
                data.add(i, temp);
            }
        }

    }
}
